package com.cqs.leetcode.string;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * lixw
 * 2023/11/5
 */
public class Solution187 {

    //18个1
    private final static int MINUS_BITS = 0x3FFFF;

    /**
     * 统计子串的频率
     * <p>
     * 子串->数字
     *
     * @param s
     * @return
     */
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> list = new ArrayList<>();
        if (s.length() <= 10) return list;
        int val = 0;
        for (int i = 0; i < 10; i++) {
            val = 4 * val + mapping(s.charAt(i));
        }
        Map<Integer, Integer> fres = new HashMap<>(s.length() - 10);
        fres.put(val, 1);
        for (int i = 10; i < s.length(); i++) {
            val = 4 * (val & MINUS_BITS) + mapping(s.charAt(i));
            int fre = fres.getOrDefault(val, 0) + 1;
            if (fre == 2) list.add(s.substring(i - 9, i + 1));
            if (fre <= 2) fres.put(val, fre);
        }
        return list;
    }


    private int mapping(Character c) {
        switch (c) {
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            default:
                return 3;
        }
    }
}
